import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 1792. 最大平均通过率
 * https://leetcode-cn.com/problems/maximum-average-pass-ratio/
 */
public class Solutions_1792 {
    public static void main(String[] args) {
//        int[][] classes = {{1, 2}, {3, 5}, {2, 2}};
//        int extraStudents = 2;  // output: 0.78333

        int[][] classes = {{2, 4}, {3, 9}, {4, 5}, {2, 10}};
        int extraStudents = 4;  // output: 0.53485

        double result = maxAverageRatio(classes, extraStudents);
        System.out.println(result);
    }

    /**
     * 解题思路：优先队列
     * 加入 1 个学生后，能够提升更大班级通过率的排在最前面
     */
    public static double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<double[]> heap = new PriorityQueue<>(new Comparator<double[]>() {
            @Override
            public int compare(double[] o1, double[] o2) {
                // o1 班级被分配聪明学生后，能够提升的通过率
                double ans1 = ((o1[0] + 1) / (o1[1] + 1) - (o1[0] / o1[1]));
                // o2 班级被分配聪明学生后，能够提升的通过率
                double ans2 = ((o2[0] + 1) / (o2[1] + 1) - (o2[0] / o2[1]));

                // 升序排列：即能够提升更大通过率的排在前面
                // 1：左值在后面
                // -1：左值在前面
                if (ans1 < ans2) {
                    return 1;
                } else {
                    return -1;
                }
            }
        });
        for (int[] arr : classes) {
            // 入队列时，将 int 类型数组转换成 double 型数组
            heap.add(new double[]{arr[0], arr[1]});
        }
        // 将 extraStudents 个学生，分配到 能够最大提升班级通过率 的班级中
        while (extraStudents > 0) {
            double[] maxClass = heap.poll();
            maxClass[0] += 1;
            maxClass[1] += 1;
            // 继续放入优先队列中
            heap.add(maxClass);
            extraStudents --;
        }
        double res = 0;

        // 计算年级通过率
        while (!heap.isEmpty()) {
            double[] cur = heap.poll();
            res += cur[0] / cur[1];
        }
        res /= classes.length;
        return res;
    }
}
